import Queue from '@/sources/Queue/useDcl';
import BST, { BstNode } from './index'
import Assert from '@/utils/assets'
export const test = () => {
    const bst = new BST();
    const assert = new Assert()
    const arr = [43, 21, 19, 60, 44]
    // debugger
    bst.batchAdd(arr);


    // assert.type('height').expect(bst.heightUseArr()).toBe(5)
    // assert.type('rootHeight').expect(bst.heightUseArr(84)).toBe(2)
    assert.type('isComplete').expect(bst.isComplete()).toBe(true)

    // debugger
    // bst.preOrder(undefined, (ele) => {
    //     console.log(ele)
    //     if (ele === 15) return true
    //     return false
    // })
    // console.log('=============')
    // // console.log('=============')
    // // bst.preOrderIterator();
    // bst.inOrder(undefined, (ele) => {
    //     console.log(ele)
    //     return false
    // })
    // console.log('=============')
    // bst.inOrderIterator()
    
    // bst.postOrder()
    // console.log('=============')
    // bst.postOrderIterator();

    // assert.type('height').expect(bst.height()).toBe(9)
    // assert.type('rootHeight').expect(bst.height(4)).toBe(9)
    // assert.type('no exist').expect(bst.height(1000)).toBe(0)


    // depth
    // assert.type('depth').expect(bst.depth()).toBe(8)
    // assert.type('depth').expect(bst.depth(33)).toBe(2)

    // const root = bst.getRoot();
    // print(bst)
    // debugger
    // bst.remove(30);
    // console.log(root)




    // assert.type('contains').expect(bst.contains(30)).toBe(true)
    // assert.type('contains').expect(bst.contains(300)).toBe(false)
    // assert.type('accessor').expect(bst.accessor(bst.getRoot()!)!.value).toBe(29)
    // assert.type('successor').expect(bst.successor(bst.getRoot()!)!.value).toBe(31)
    // console.log(bst.successor())
    // console.log(bst.accessor())


    print(bst)
}

/**
 * 打印二叉树
 * @param bst 
 */
export const print = <T>(bst: BST<T>) => {
    // 是空的
    if (bst.isEmpty()) return;
    let root = bst.getRoot();
    const queue = new Queue<BstNode<T>>();
    queue.enQueue(root!);
    let levelSize = 1,
        height = 0;
    const hInfo: Record<string, Array<BstNode<T>>> = {
        l1: []
    }

    while (!queue.isEmpty()) {
        const node = queue.deQueue()!;
        levelSize--;
        if (node === root) {
            // str += `${node.value} \n`
            hInfo.l1.push(node!)
        }
        // parent = node;
        // 左节点
        if (node.left) {
            queue.enQueue(node.left)
        }
        // 右节点
        if (node.right) {
            queue.enQueue(node.right)
        }

        if (levelSize === 0) {
            // 该层已经访问过了
            // 此时在队列的都是下一层
            levelSize = queue.size();

            const tmp = height + 2;
            queue.forEach((ele) => {
                (hInfo['l' + (tmp)] || (hInfo['l' + (tmp)] = [])).push(ele!)
            })

            // 更新层数
            height++
        }
    }
    printBstTree(hInfo)
}

/**
 * 打印二叉树
 * @param bst 
 */
export const print2 = <T>(root: BstNode<T> | null) => {
    // 是空的
    if (root == null) return;
    const queue = new Queue<BstNode<T>>();
    queue.enQueue(root!);
    let levelSize = 1,
        height = 0;
    const hInfo: Record<string, Array<BstNode<T>>> = {
        l1: []
    }

    while (!queue.isEmpty()) {
        const node = queue.deQueue()!;
        levelSize--;
        if (node === root) {
            // str += `${node.value} \n`
            hInfo.l1.push(node!)
        }
        // parent = node;
        // 左节点
        if (node.left) {
            queue.enQueue(node.left)
        }
        // 右节点
        if (node.right) {
            queue.enQueue(node.right)
        }

        if (levelSize === 0) {
            // 该层已经访问过了
            // 此时在队列的都是下一层
            levelSize = queue.size();

            const tmp = height + 2;
            queue.forEach((ele) => {
                (hInfo['l' + (tmp)] || (hInfo['l' + (tmp)] = [])).push(ele!)
            })

            // 更新层数
            height++
        }
    }
    printBstTree(hInfo)
}


/**
 * 打印出二叉树
 * @param d 
 */
const printBstTree = (d: Record<string, any>) => {
    const keys = Object.keys(d),
        len = keys.length;
    // root偏移的距离
    const padLen = 5;

    // 记录层数
    let desc = 4;

    let str = ''

    for (let i = 0; i < len; i++) {
        const sub = d[keys[i]],
            len = sub.length;
        for (let j = 0; j < len; j++) {
            if (i === 0) {
                // 第一层
                sub[j].pad = padLen
                str += `${pad(padLen)}${sub[j].value}`
            } else {
                // debugger
                // 不是第一层 
                const node = sub[j];
                // if (node.value === 15) debugger
                if (node.isLeft()) {
                    // 是左孩子
                    if (j === 0) {
                        // 该层第一个孩子
                        str += `${pad(node.parent.pad - desc) + sub[j].value}`
                        node.pad = node.parent.pad - desc
                    } else {
                        // 上一个节点的pad
                        const tmp = sub[j - 1].pad + 8
                        str += `${pad(8) + sub[j].value}`
                        node.pad = tmp
                    }

                } else {
                    // 是右孩子
                    if (j === 0) {
                        // 该层的第一个孩子
                        str += `${pad(node.parent.pad + desc) + sub[j].value}`
                        node.pad = node.parent.pad + desc
                    } else {
                        // debugger
                        const tmp = sub[j - 1].pad + 8
                        str += `${pad(8) + sub[j].value}`
                        node.pad = tmp
                    }
                }
            }
        }
        str += '\n'
    }

    console.log(str);
    // console.log('偏移:', pad(padLen).length)


}


/**
 * 填空
 * @param level 
 */
const pad = (level: number) => {
    return ''.padEnd(level, ' ')
}